/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-03-11
 * Time: 14:56
 */

class Node {
    public int data;//存储数据
    public Node next;//每一个节点的地址
    //构造一个方法
    public Node(int data) {//一个节点包括下一节点的地址和数据
        this.data=data;
        this.next=null;
    }
}

public class MyLinkList {
    //创建一个头结点
    public Node head;//刚开始头结点指向null
    public void addList(int data) {//头插
        Node node =new Node(data);
        if(this.head==null) {//判断刚开始头结点指向空没有存储数据
            this.head=node;
            return;
        }
        node.next= this.head;
        this.head=node;
    }

    public void addLast(int data) {

        Node node =new Node(data);
        if(this.head==null) {//判断刚开始头结点指向空没有存储数据
            this.head=node;
            return;
        }
        //首先我们先找到尾
        Node cur =this.head;
        while(cur.next!=null) {
            cur=cur.next;
        }
        //此时已经找到尾了
        cur.next=node;

    }

    public void display() {
        Node cur =this.head;
        while(cur!=null) {
            System.out.print(cur.data);
            if(cur.next!=null){
                System.out.print("->");
            }
            cur=cur.next;
        }
        System.out.println();
    }

    public boolean contains(int key) {
        Node cur =this.head;
        while(cur!=null) {
            if(cur.data==key) {
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

    public int size() {
        Node cur =this.head;
        int count=0;
        while(cur!=null) {
            ++count;
            cur=cur.next;
        }
        return count;
    }

    private Node searchIndex(int index) {
     //检查index的合法性
        if(index<0||index>this.size()) {
            throw new RuntimeException("位置错误");
        }
        int gap =index-1;
        Node cur =this.head;
        while((gap--)!=0) {
          cur=cur.next;
        }
        return cur;
    }

    public void addIndex(int index,int data) {
        //判断头插
        Node node =new Node(data);
        if(index==0) {
            addList(data);
            return;
        }
        //判断尾插
        if(index==this.size()) {
            addLast(data);
            return ;
        }
        //找到下一个节点的地址
        Node cur = searchIndex(index);
        //开始插入
        node.next=cur.next;
        cur.next=node;
    }

    //删除所有出现关键字的节点
    public void removeAllKey1(int key) {
        Node prev =this.head;
        Node cur =prev.next;
        while(cur!=null) {
            if(cur.data==key) {
                prev.next=cur.next;
                cur=cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        if(head.data==key) {
            head=head.next;
            return;
        }
    }
//___________________________________________
         //删除所有值为key的元素
        public void removeAllKey(int key) {
            if(head==null) {
                return;
            }
         Node prev =this.head;
         Node cur =prev.next;
             while(cur!=null) {
              if(cur.data==key) {
                  prev.next=cur.next;
                  cur=cur.next;
              }else {
                  prev=cur;
                  cur=cur.next;
              }
         }
          if(head.data==key) {
              head=head.next;
              return;
          }
    }
    public void remove(int key) {
        if(head==null) {
            return;
        }
        if(head.data==key) {
            head=head.next;
            return;
        }
        Node prev =this.head;
        Node cur =prev.next;
        while(cur!=null) {
            if(cur.data==key) {
                prev.next=cur.next;
                cur=cur.next;
                return;
            }else {
                prev=cur;
                cur=cur.next;
            }
        }
    }

    public void reverse() {
        if(this.head==null) {
            return ;
        }
        Node cur=this.head;
        Node newHead=null;
        while(cur!=null) {
            Node next =this.head.next;
            if(newHead==null) {
                newHead=cur;
            }else {
                cur.next=newHead;
                newHead=cur;
            }
            cur=next;
        }

    }

}
